The present invention pertains to electronic data processing, and more specifically concerns a new architecture for providing indexed indirect addressing of instruction operands in memory.
The addressing mode known as "indexed indirect" adds an operand address contained in an instruction to an index value to form a further address. The memory contents at this further address are treated as yet another address and added to another index value, this sum then being used to address memory for the operand. This process may be repeated any number of times for multi-level indirection, each level having its own index value.
Indexed indirect addressing is a valuable capability in an instruction set, especially in the processing of complex data structures such as lists, queues, stacks, and so forth. On the other hand, this capability does extract a penalty, an overhead which must be minimized for most efficient usage of the available bit combinations for instructions and memory addresses.
Previous approaches in this area fall into three broad types.
First, instruction operation codes can merely be duplicated to provide indirection. For example, if op-codes are one byte long, and if MOVE A,B means "move the memory contents of address A to the memory location at address B", then MOVEI A(I),B COULD mean "use the contents of address A, added to displacement value I, as the address of the operand to be moved to address B". The op-codes for MOVE AND MOVEI occupy two different bit combinations (code points) of the 256 available op-codes. Providing the other two forms of MOVE, namely A,B(I) and A(I),B(I), requires two more code points, merely for this one instruction. Obviously, this method requires a large op-code space; or, conversely, it reduces the number of different instructions which can be accommodated in a space of a given size. Moreover, only a single level of indirection is Possible without even more extravagant use of op-code space.
Second, addressing-mode bits in each instruction, separate from the op-code, can be used to specify whether each operand in that instruction is to be direct or indirect. This method increases the total length of the instruction by at least one bit for each operand; or, by appropriating a bit which could otherwise be used in the address itself, it decreases the range of possible operand values by half. Here again, multi-level indirection is possible only at the expense of further mode bits in every instruction.
The third broad category places an indirect-mode bit in every address word in memory. When any instruction fetches an operand, it examines its mode bit. If the bit is off, that word itself is the operand; if the bit is on, the word (or its sum with an index value) is used to address memory again. This process repeats until the mode bit of an addressed word is off. While this method does permit multi-level indirection, it decreases the range of addressable memory by half. For a 16-bit memory address, only 32,768 of the possible 65,536 bit combinations represent valid addresses; the address has effectively become only 15 bits. This penalty is paid by all instructions, whether they ever use this feature or not.